package main.Q1_100;

import java.util.*;

public class Q81_90 {
    public static void main(String[] args) {
        System.out.println("Question81：搜索旋转排序数组Ⅱ");
        System.out.println("Question82：删除排序链表中的重复元素Ⅱ");
        System.out.println("Question83：删除排序链表中的重复元素");
        System.out.println("Question84：柱状图中最大的矩形");
        System.out.println("Question85：最大矩形");
        System.out.println("Question86：分隔链表");
        System.out.println("Question87：");
        System.out.println("Question88：合并两个有序数组");
        System.out.println("Question89：格雷编码");
        System.out.println("Question90：子集Ⅱ");
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Question81{
    public boolean search(int[] nums, int target) {
        int left=0,right= nums.length-1;
        Arrays.sort(nums);
        while (left<=right){
            int mid=(left+right)/2;
            if (nums[mid]==target) return true;
            if (nums[mid]<target) left=mid+1;
            else right=mid-1;
        }
        return false;
    }
}

class Question82{
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
//        if (head==null||head.next==null) return head;//无节点或仅有一个节点
//        ListNode pre=head,last=head.next;
//        while (last!=null){
//            if (pre.val==last.val){
//                while (last!=null&&last.val== pre.val) {
//                    last=last.next;
//                }
//                pre.next=last;
//            }else {
//                pre = pre.next;
//                last = last.next;
//            }
//        }
//        return head;
    }
}

class Question83{
    public ListNode deleteDuplicates(ListNode head) {
        if (head!=null) {
            ListNode result = head, pre = head, next = head.next;
            while (next != null) {
                if (pre.val != next.val) {//两节点值不同
                    next = next.next;
                    pre = pre.next;
                } else {//两节点值相同
                    pre.next = next.next;
                    next = next.next;
                }
            }
            return result;
        }else return head;
    }
}

class Question84{
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];

        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        mono_stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}

class Question85{
    public int maximalRectangle(char[][] matrix) {
        String[] ma=new String[matrix.length];
        for (int i=0;i<ma.length;i++) ma[i]=String.valueOf(matrix[i]);
        int m = ma.length;
        if (m == 0)  return 0;
        int n = ma[0].length();
        int[][] left = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (ma[i].charAt(j) == '1') {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (ma[i].charAt(j) == '0') continue;
                int width = left[i][j];
                int area = width;
                for (int k = i - 1; k >= 0; k--) {
                    width = Math.min(width, left[k][j]);
                    area = Math.max(area, (i - k + 1) * width);
                }
                ret = Math.max(ret, area);
            }
        }
        return ret;
    }
}

class Question86{
    public ListNode partition(ListNode head, int x) {
        ListNode unSmallVir = new ListNode(), smallVir = new ListNode();
        ListNode unSmallTemp = unSmallVir, sTemp = smallVir;
        while (head != null) {
            if (head.val < x) {//小于节点
                sTemp.next = new ListNode(head.val);
                sTemp = sTemp.next;
            } else {
                unSmallTemp.next = new ListNode(head.val);
                unSmallTemp = unSmallTemp.next;
            }
            head = head.next;
        }
        ListNode resultVir = new ListNode(), resultTemp = resultVir;
        if (smallVir.next != null) {//小于节点接入
            resultTemp.next = smallVir.next;
            resultTemp = sTemp;
        }
        if (unSmallVir.next != null) {//大于等于节点接入
            resultTemp.next = unSmallVir.next;
        }
        return resultVir.next;
    }
}

class Question88{
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) nums1[i] = sorted[i];
    }
}

class Question89{
    public List<Integer> grayCode(int n) {
        List<Integer> list=new ArrayList<>();
        list.add(0);//初始
        for (int i=0;i<n;i++){
            List<Integer> temp=new ArrayList<>(list);
            Collections.reverse(temp);//翻转
            for (int j=0;j<temp.size();j++) temp.set(j, temp.get(j)+(int)Math.pow(2,i));
            list.addAll(temp);
        }
        return list;
    }
}

class Question90{
    List<List<Integer>> list=new ArrayList<>();
    public void process(int[] nums,int start,List<Integer> lastList){
        list.add(new ArrayList<>(lastList));
        for (int i=start;i< nums.length;i++){
            if (i==start){
                lastList.add(nums[i]);
                process(nums,i+1,lastList);
                lastList.remove(lastList.size()-1);
                continue;
            }
            if (i+1< nums.length&&nums[start]!=nums[i]){
                lastList.add(nums[i]);
                process(nums,i+1,lastList);
                lastList.remove(lastList.size()-1);
            }
        }
    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> retList = new ArrayList<>();
        retList.add(new ArrayList<>());
        if(nums == null || nums.length == 0) return retList;
        Arrays.sort(nums);
        List<Integer> tmp = new ArrayList<>();
        tmp.add(nums[0]);
        retList.add(tmp);
        if(nums.length == 1) return retList;
        int lastLen = 1;
        for(int i = 1; i < nums.length; i++){
            int size = retList.size();
            if(nums[i] != nums[i-1]){
                lastLen = size;
            }
            for(int j = size - lastLen; j < size; j++){
                List<Integer> inner = new ArrayList(retList.get(j));
                inner.add(nums[i]);
                retList.add(inner);
            }
        }
        return retList;
    }
}